package 剑指offer_专项突击版.中等;

import 分类.前缀和;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入:nums = [1,1,1], k = 2
 * 输出: 2
 * 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/QTMn0o
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/11/3 10:37
 */
public class _010_和为k的子数组 implements 前缀和 {
    
    public static void main(String[] args) {
        _010_和为k的子数组 a = new _010_和为k的子数组();
        a.subarraySum(new int[]{1}, 0);
    }

    /**
     * 前缀和
     * 把0到i的数字和设置到map的key中，把和出现的次数记录到value中，初始化0出现的次数
     * https://leetcode.cn/problems/QTMn0o/solution/qian-zhui-he-hash-table-he-wei-k-de-zi-s-knqq/
     */
    public int subarraySum(int[] nums, int k) {
        
        int preSum = 0, count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        // 初始化0的情况
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            // 累计数组的和
            preSum += nums[i];
            // 需要查看 preSum - k（剩下需要满足的值）是否已经在map中了 
            // 计算剩下需要满足k的值
            int val = preSum - k;
            if (map.containsKey(val)) {
                // 存在了满足的情况
                count += map.get(val);
            }
            map.put(preSum, map.getOrDefault(preSum, 0) + 1);
        }
        return count;
    }

    /**
     * 有了负数和零 不能用滑动窗口
     * 因为存在了负数就无法知道应该是left移动还是right移动了
     *
     */
    public int subarraySum1(int[] nums, int k) {
        int left = 0, right = 0;
        int sum = 0;
        int count = 0;
        while(right < nums.length) {
            sum += nums[right];
            while(sum > k) {
                sum -= nums[left];
                left++;
            }
            if (sum == k) {
                count++;
            }
            right++;
        }
        
        return count;
    }
    
}
